﻿namespace Leetcode.N0307.V2;

public class NumArray
{

    private readonly int[] sums;
    private readonly int[] nums;
    public NumArray(int[] nums)
    {
        this.nums = nums;
        var sLength = (int)Math.Pow(2, (int)Math.Ceiling(Math.Log2(nums.Length)));
        this.sums = new int[sLength];
        this.CalcSum(0, 0, this.nums.Length - 1);
    }

    private int CalcSum(int sIndex, int nFrom, int nTo)
    {
        if (nFrom == nTo)
        {
            return this.nums[nFrom];
        }
        var m = nFrom + (nTo - nFrom) / 2;
        var s1 = this.CalcSum(sIndex * 2 + 1, nFrom, m);
        var s2 = this.CalcSum(sIndex * 2 + 2, m + 1, nTo);
        this.sums[sIndex] = s1 + s2;
        return this.sums[sIndex];
    }


    public void Update(int index, int val)
    {
        this.UpdateSum(0, 0, this.nums.Length - 1, index, val);
    }

    public int UpdateSum(int sIndex, int nFrom, int nTo, int nIndex, int val)
    {
        int d;
        if (nFrom == nTo)
        {
            d = val - this.nums[nIndex];
            this.nums[nIndex] = val;
            return d;
        }
        var m = nFrom + (nTo - nFrom) / 2;
        if (m >= nIndex)
        {
            d = this.UpdateSum(sIndex * 2 + 1, nFrom, m, nIndex, val);
        }
        else
        {
            d = this.UpdateSum(sIndex * 2 + 2, m + 1, nTo, nIndex, val);
        }

        this.sums[sIndex] += d;
        return d;
    }

    public int SumRange(int left, int right)
    {
        return this.SumRange(0, 0, this.nums.Length - 1, left, right);
    }

    private int SumRange(int sIndex, int nFrom, int nTo, int left, int right)
    {
        if (left == right)
        {
            return this.nums[left];
        }

        if (nFrom == left && nTo == right)
        {
            return this.sums[sIndex];
        }

        var m = nFrom + (nTo - nFrom) / 2;
        int s1 = 0;
        int s2 = 0;
        if (left <= m)
        {
            s1 = this.SumRange(sIndex * 2 + 1, nFrom, m, left, Math.Min(m, right));
        }
        if (right > m)
        {
            s2 = this.SumRange(sIndex * 2 + 2, m + 1, nTo, Math.Max(m + 1, left), right);
        }
        return s1 + s2;
    }
}
